package com.learn.algorithm_695;

import org.junit.Test;

/**
 * 695. 岛屿的最大面积
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-area-of-island
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author gatts, 2022/1/19 17:06:29
 */
public class BiggestIsland {

    @Test
    public void test() {
        int[][] grid = {
                {1,1,0,0,0},
                {1,1,0,0,0},
                {0,0,1,0,0},
                {0,0,0,1,1}
        };

        System.out.println("最大岛屿面积：" + maxAreaOfIsland(grid));
    }

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {

                if (grid[i][j] == 1) {
                    maxArea = Math.max(deepFirstSearch(grid, i, j), maxArea);
                    System.out.println("-------------岛屿分割线------------");
                }

            }
        }

        return maxArea;
    }

    /**
     * 每块陆地，遍历寻找四周相邻的陆地组成岛屿
     *
     * @param grid
     * @param row
     * @param column
     * @return
     */
    private int deepFirstSearch(int[][] grid, int row, int column) {
        // 向上下左右遍历，判断是否是陆地，是则继续循环，否则停止，直至遍历到边界
        if (row >= 0 && row < grid.length && column >= 0 && column < grid[0].length && grid[row][column] == 1) {
            System.out.println(String.format("陆地坐标：%d, %d", row, column));
            grid[row][column] = 2; // 遍历过的陆地修改标识为2，防止重复遍历

            return 1
                    + deepFirstSearch(grid, row, column - 1) // 左
                    + deepFirstSearch(grid, row, column + 1) // 右
                    + deepFirstSearch(grid, row - 1, column) // 上
                    + deepFirstSearch(grid, row + 1, column); // 下
        }
        return 0;
    }

}
